

// 排序二叉树 类
function BinaryTree() {
    //节点
    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }

    //根节点
    var root = null;

    //排序二叉树 插入节点
    var insertNode = function (node, newNode) {
        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }
    }

    //创建排序二叉树
    this.insert = function (key) {
        var newNode = new Node(key);
        if (root === null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    }

    var callback = function (key) {
        console.log(key + " ");
    }

    // 二叉树中序遍历（左 中 右）
    var inOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    }

    // 中序遍历（对排序二叉树进行中序遍历 得到有序的数列）
    this.inOrderTraverse = function () {
        inOrderTraverseNode(root, callback);
    }

    // 二叉树前序遍历 （中 左 右）
    var preOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            callback(node.key);
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
        }

    }

    // 前序遍历（用于复制二叉树）
    this.preOrderTraverse = function () {
        preOrderTraverseNode(root, callback);
    }

    //二叉树后序遍历 （左 右 中）
    var postOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            postOrderTraverseNode(node.left, callback);
            postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    }

    // 后序遍历
    this.postOrderTraverse = function () {
        postOrderTraverseNode(root, callback);
    }

    // 树的高度
    var maxDepth = function (node) {
        if (node === null) return 0;
        var lh = maxDepth(node.left);
        var rh = maxDepth(node.right);
        return lh > rh ? lh + 1 : rh + 1;
    }

    this.getHeight = function () {
        var hegiht = maxDepth(root);
        console.log("树的高度为：" + hegiht);
    }

    //最大值 和 最小值
    var minNode = function (node) {
        if (node === null)
            return;
        if (node.left === null) {
            return node;
        }
        else {
            return minNode(node.left);
        }
    }

    var maxNode = function (node) {
        if (node === null)
            return;
        if (node.right === null) {
            return node;
        }
        else {
            return maxNode(node.right);
        }
    }

    this.getMaxAndMin = function () {
        var max = maxNode(root);
        var min = minNode(root);
        console.log("max key：" + max.key);
        console.log("min key：" + min.key);
    }

    var findMinNode = function (node) {
        if (node) {
            while (node && node.left) {
                node = node.left;
            }
            return node;
        }
        return null;
    }

    var findMaxNode = function (node) {
        if (node) {
            while (node && node.right) {
                node = node.right;
            }
            return node;
        }
        return null;
    }

    //查找
    var searchNode = function (node, key) {
        if (node === null) {
            return false;
        }

        if (node.key === key)
            return true;
        else if (key > node.key)
            return searchNode(node.right, key);
        else if (key < node.key)
            return searchNode(node.left, key);
    }

    this.search = function (key) {
        if (searchNode(root, key))
            console.log(key + " is found");
        else
            console.log(key + " is not found");
    }

    //删除节点
    var removeNode = function (node, key) {
        if (node === null)
            return null;

        if (key < node.key) {
            node.left = removeNode(node.left, key);
            return node;
        } else if (key > node.key) {
            node.right = removeNode(node.right, key);
            return node;
        } else {
            //第一种情况：删除节点无子节点
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }
            //第二种情况：删除节点只有右孩子
            if (node.left === null) {
                node = node.right;
                return node;
            }
            //第三种情况：删除节点只有左孩子
            if (node.right === null) {
                node = node.left;
                return node;
            }
            //第四种情况：删除节点有左孩子和右孩子
            if (node.left !== null && node.right !== null) {
                //找到右子树的最小节点
                var mark = findMinNode(node.right);
                //更新
                node.key = mark.key;
                //删除右子树的最小节点
                node.right = removeNode(node.right, mark.key);
            }

        }
    }

    this.remove = function (key) {
        return removeNode(root, key);
    }

}


// node binarytree/binary_tree.js
//创建排序二叉树
var nodes = [89, 34, 98, 122, 3, 10000, -9, 877, 0, 555, 76, 888, 6, 889, 1, 2];
var binaryTree = new BinaryTree();
nodes.forEach(function (key) {
    binaryTree.insert(key);
});
//前序遍历
binaryTree.preOrderTraverse();
console.log("---------------------------");

//中序遍历
binaryTree.inOrderTraverse();
console.log("---------------------------");

//后序遍历
binaryTree.postOrderTraverse();
console.log("---------------------------");

// 高度
binaryTree.getHeight();

//最大最小值
binaryTree.getMaxAndMin();

//查找
binaryTree.search(3);
binaryTree.search(4);
binaryTree.search(5);
